%%%-------------------------------------------------------------------
%%% @author Plamen Dragozov <plamen@dragozov.com>
%%% @copyright (C) 2010, Plamen Dragozov
%%% @doc <p>A <a href="http://en.wikipedia.org/wiki/Treap">Treap</a> is a tree data structure in which each node has a priority assigned at insertion.<br/> 
%%% While nodes in the tree are still sorted by their keys, they are also kept vertically sorted by 
%%% their priority (i.e. a higher priority is closer to the root). <br/>
%%% By ensuring that the generated priorities are uniformly spread the treap's tree can be kept well
%%% ballanced, which avoids the need of rebalancing it regularly.</p>
%%% <p>This implementation uses random:uniform(MAX) to generate the priority of each node.
%%% The treap module was written as a drop-in replacement for the standard Erlang module <em>dict</em> and implements all its methods, 
%%% but with the corresponding performance differences.<br/>
%%% It also provides additional methods for querying and manipulating a treap in a sorted order 
%%% (both ascending and descending), for splitting a treap (so that one of the resulting treaps contains only
%%% keys smaller and the other keys only greater than a given key), for exporting a treap to a dict, list, JSON and
%%% XML string etc.
%%% </p>
%%% @end
%%% Created : 28 Jul 2010
%%%-------------------------------------------------------------------
-module(treap).

%-define(NOTEST, true).
%-include_lib("eunit/include/eunit.hrl").

%% API

%%structural
-export([append/3, append_list/3, erase/2, merge/3, new/0, split/2, store/3, unsplit/2, update/3, update/4, update_counter/3]).

%%query
-export([count_values/1, find/2, fetch/2, fetch_keys/1, fetch_keysl/1, fetch_keysr/1, is_key/2, size/1]).

%%functional
-export([filter/2, fold/3, foldl/3, foldr/3, foreach/2, foreachl/2, foreachr/2, foreach_spawn/2, map/2]).

%%conversion
-export([from_list/1, from_dict/1, from_dict/2, to_dict/1, to_dict/2, to_json/1, to_list/1, to_listl/1, to_listr/1, to_xml/1]).

%%
-export([debug_tree/1]).

-define(MAX_PRIORITY, 2147483647). % 16#ffffffff div 2
-define(SPLIT_TAG, '!SPLIT').
-define(UNSPLIT_TAG, '!UNSPLIT').

-type(treap() :: empty | {integer(), any(), [any()], treap(), treap()}).

-on_load(seed/0).

%called at the module load time
seed() ->
    random:seed(now()),
    ok.

%%%===================================================================
%%% API
%%%===================================================================

%%--------------------------------------------------------------------
%% @doc Returns a new empty treap.
%%
%% @spec new() -> Treap :: treap()
%% @end
%%--------------------------------------------------------------------
-spec new() -> treap().
new()->
    empty.

%%--------------------------------------------------------------------
%% @doc This function appends a new Value to the current list of values associated with Key 
%% (or inserts a new list containing Value if the Key was not found).
%% @spec append(Key :: any(), Value :: any(), Treap :: treap()) -> NewTreap :: treap()
%% @end
%%--------------------------------------------------------------------
-spec append(any(), any(), treap()) -> treap().
append(Key, Value, Treap) ->
    Fun = fun(OldValues) -> 
		  [Value|OldValues]
	  end,
    update(Key, Fun, Value, Treap).

%%--------------------------------------------------------------------
%% @doc This function appends a list of values Values to the current list of values associated with Key.
%% (or inserts the new list if the Key was not found).
%% 
%% @spec append_list(Key :: any(), Values :: [any()], Treap :: treap()) -> NewTreap :: treap()
%% @end
%%--------------------------------------------------------------------
-spec append_list(any(), [any()], treap()) -> treap().
append_list(_, [], Treap) -> Treap;
append_list(Key, [_H|_T] = Values, Treap) ->
    Fun = fun(OldValues) ->
		  Values ++ OldValues
	  end,
    update(Key, Fun, Values, Treap);
append_list(Key, Value, Treap) ->
    append(Key, Value, Treap).

%%--------------------------------------------------------------------
%% @doc This function erases all items with a given key from a dictionary.
%% @spec erase(Key :: any(), Treap :: treap()) -> NewTreap :: treap()
%% @end
%%--------------------------------------------------------------------
-spec erase(any(), treap()) -> treap().
erase(_, empty) ->
    empty;
erase(Key, {_, Key, _, Before, After}) ->
    case {Before, After} of
	{empty, empty} ->
	    empty;
	{Before, empty} ->
	    Before;
	{empty, After} ->
	    After;
	{{BeforePriority, BeforeKey, BeforeValues, BeforeBefore, BeforeAfter}, {AfterPriority, AfterKey, AfterValues, AfterBefore, AfterAfter}} ->
	    case AfterPriority >= BeforePriority of
		true ->
		    {AfterPriority, AfterKey, AfterValues, erase(Key, {0, Key, null, Before, AfterBefore}), AfterAfter}; 
		_ ->
		    {BeforePriority, BeforeKey, BeforeValues, BeforeBefore, erase(Key, {0, Key, null, BeforeAfter, After})}
	    end
    end;
erase(Key, {NodePriority, NodeKey, NodeValues, Before, After}) when Key < NodeKey ->
    {NodePriority, NodeKey, NodeValues, erase(Key, Before), After};
erase(Key, {NodePriority, NodeKey, NodeValues, Before, After}) ->
    {NodePriority, NodeKey, NodeValues, Before, erase(Key, After)}.

%%--------------------------------------------------------------------
%% @doc This function stores a Key - Value pair in a treap.<br/>
%% If the Key already exists in Treap, the associated list of values is replaced by [Value].
%%
%% @spec store(Key :: any(), Value :: any(), Treap :: treap()) -> NewTreap :: treap()
%% @end
%%--------------------------------------------------------------------
-spec store(any(), any(), treap()) -> treap().
store(Key, [_|_] = Value, Treap) ->
    update(Key, fun(_) -> Value end, Value, Treap);
store(Key, Value, Treap) ->
    update(Key, fun(_) -> [Value] end, Value, Treap).

%%--------------------------------------------------------------------
%% @doc This function searches for a key in a treap. <br/> 
%% Returns {ok, Values} where Values is a list of the values associated with Key,
%% or error if the key is not present in the treap.
%%
%% @spec find(Key :: any(), Treap :: treap()) -> error | {ok, Values :: [any()]}
%% @end
%%--------------------------------------------------------------------
-spec find(any(), treap()) -> error | {ok, any()}.
find(_, empty) ->
    error;
find(Key, {_, Key, NodeValues, _, _}) ->
    {ok, NodeValues};
find(Key, {_, NodeKey, _, Before, _}) when Key < NodeKey ->
    find(Key, Before);
find(Key, {_, _, _, _, After}) ->
    find(Key, After).

%%--------------------------------------------------------------------
%% @doc This function returns the value associated with Key in the treap Treap.<br/>
%% <em>fetch</em> assumes that the Key is present in the treap and an exception
%% is generated if Key is not in the treap.
%% @spec fetch(Key :: any(), Treap :: treap()) -> Values :: [any()]
%% @end
%%--------------------------------------------------------------------
-spec fetch(any(), treap()) -> any().
fetch(Key, Treap) -> 
    case find(Key, Treap) of
	error ->
	    erlang:error({not_found, Key});
	{ok, Value} ->
	    Value
    end.

%%--------------------------------------------------------------------
%% @doc This function returns a list of all keys in the treap.
%% @spec fetch_keys(Treap :: treap()) -> Values :: [any()]
%% @end
%%--------------------------------------------------------------------
-spec fetch_keys(treap()) -> [any()].
fetch_keys(Treap) ->
    Fun = fun(Key, _, Acc) ->
			  [Key|Acc]
		  end,
    fold(Fun, [], Treap).

%%--------------------------------------------------------------------
%% @doc This function returns a list of all keys in the treap in an <em>ascending</em> order.
%% @spec fetch_keysl(Treap :: treap()) -> Values :: [any()]
%% @end
%%--------------------------------------------------------------------
-spec fetch_keysl(treap()) -> [any()].
fetch_keysl(Treap) ->
    Fun = fun(Key, _, Acc) ->
		  [Key|Acc]
	  end,
    %they come reversed, so use foldr
    foldr(Fun, [], Treap).

%%--------------------------------------------------------------------
%% @doc This function returns a list of all keys in the treap in a <em>descending</em> order.
%% @spec fetch_keysr(Treap :: treap()) -> Values :: [any()]
%% @end
%%--------------------------------------------------------------------
-spec fetch_keysr(treap()) -> [any()].
fetch_keysr(Treap) ->
    Fun = fun(Key, _, Acc) ->
			  [Key|Acc]
		  end,
    %they come reversed, so use foldl
    foldl(Fun, [], Treap).

%%--------------------------------------------------------------------
%% @doc This function splits the Treap in 2 separate treaps:
%% <ul>
%% <li>Treap1, containing all keys smaller or equal to Key.</li> 
%% <li>Treap2 containing all keys greater than Key.</li>
%% </ul>
%% @spec split(Key :: any(), Treap :: treap()) -> {Treap1 :: treap(), Treap2 :: treap()}
%% @end
%%--------------------------------------------------------------------
-spec split(any(), treap()) -> {treap(), treap()}.
split(Key, Treap) ->
    {?MAX_PRIORITY, {?SPLIT_TAG, Key}, _, Before, After} = update({?SPLIT_TAG, Key}, fun(X) -> X end, null, Treap),
    {Before, After}.

%%--------------------------------------------------------------------
%% @doc This function merges two treaps that meet the requirement that the largest 
%% key in one of the treaps is smaller than the smallest key in the other 
%% (i.e. they could have been produced by calling split/2).<br/> 
%% <i>eThis is equivalent to undoing split/2</i>
%%
%% @spec unsplit(Treap1 :: treap(), Treap2 :: treap()) -> Treap3 :: treap()
%% @end
%%--------------------------------------------------------------------
-spec unsplit(treap(), treap()) -> treap().
unsplit({_, K1, _, _, _} = B, {_, K2, _, _, _} = A) when K1 > K2 ->
    unsplit(A, B);
unsplit(B, A) ->
    erase(?UNSPLIT_TAG, {?MAX_PRIORITY, ?UNSPLIT_TAG, [null], B, A}).

%%--------------------------------------------------------------------
%% @doc Returns NewTreap, which is a treap of only the keys and values in Treap for which Pred(Key, Value) is true.
%%
%% @spec filter(Pred :: function(Key :: any(), Value :: [any()]), Treap :: treap()) -> NewTreap :: treap() 
%% @end
%%--------------------------------------------------------------------
-spec filter(function(), treap()) -> treap().
filter(_, empty) ->
    empty;
filter(Pred, {P, K, V, B, A}) ->
    NewT = {P, K, V, filter(Pred, B), filter(Pred, A)},
    case Pred(K, V) of
	true ->
	    NewT;
	_ -> 
	    erase(K, NewT)
    end.

%%--------------------------------------------------------------------
%% @doc This function tests if Key is contained in the treap Treap.
%%
%% @spec is_key(Key :: any(), Treap :: treap()) -> TrueOrFalse :: boolean()
%% @end
%%--------------------------------------------------------------------
-spec is_key(any(), treap()) -> boolean().
is_key(_, empty) ->
    false;
is_key(Key, {_, Key, _, _, _}) ->
    true;
is_key(Key, {_, NodeKey, _, Before, _}) when Key < NodeKey ->
    is_key(Key, Before);
is_key(Key, {_, _, _, _, After}) ->
    is_key(Key, After).

%%--------------------------------------------------------------------
%% @doc Returns a new treap NewTreap, build by mapping the result from calling Fun(Key, OldValues) to Key for each key of Treap.
%% If the result of the function is a non-empty list it's put as the new value, else the result is first enclosed in a list.
%%
%% @spec map(Fun :: function(Key :: any(), Values :: [any()]), Treap :: treap()) -> NewTreap :: treap()
%% @end
%%--------------------------------------------------------------------
-spec map(function(), treap()) -> treap().
map(_, empty) ->
    empty;
map(Fun, {Priority, Key, Value, Before, After}) ->
    NewValue = case Fun(Key, Value) of
		   [_|_] = Result -> Result;
		   Result -> [Result]
	       end,
    {Priority, Key, NewValue, map(Fun, Before), map(Fun, After)}.

%%--------------------------------------------------------------------
%% @doc Merges two treaps, Treap1 and Treap2, to create a new treap. 
%% All the Key - Value pairs from both treaps are included in the new treap. 
%% If a key occurs in both treaps then Fun is called with the key and both values to return a new value.
%%
%% @spec merge(Fun :: function(Value1 :: [any()], Value2 :: [any()]), Treap1 :: treap(), Treap2 :: treap()) -> NewTreap :: treap()
%% @end
%%--------------------------------------------------------------------
-spec merge(function(), treap(), treap()) -> treap().
merge(_, Treap, empty) ->
    Treap;
merge(_, empty, Treap) ->
    Treap;
merge(Fun, Treap1, Treap2) ->
    Fun1 = fun(Key, Values1, Acc) ->
		  update(Key, fun(Values2) -> Fun(Key, Values1, Values2)  end, Values1, Acc)
	  end,
    fold(Fun1, Treap1, Treap2).

%%--------------------------------------------------------------------
%% @doc Converts the treap to a key/value (unordered) list.
%% @spec to_list(Treap :: treap()) -> [{Key :: any(), Values :: [any()]}]
%% @end
%%--------------------------------------------------------------------
-spec to_list(treap()) -> [{any(), any()}].
to_list(Treap) ->
    Fun = fun(Key, Value, Acc) ->
		  [{Key, Value}|Acc]
	  end,
    fold(Fun, [], Treap).

%%--------------------------------------------------------------------
%% @doc Converts the treap to a key/value list sorted by the keys in ascending order.
%% @spec to_listl(Treap :: treap()) -> [{Key :: any(), Values :: [any()]}]
%% @end
%%--------------------------------------------------------------------
-spec to_listl(treap()) -> [{any(), any()}].
to_listl(Treap) ->
    Fun = fun(Key, Value, Acc) ->
		  [{Key, Value}|Acc]
	  end,
    %they come in reversed order, so use foldr
    foldr(Fun, [], Treap).

%%--------------------------------------------------------------------
%% @doc Converts the treap to a key/value list sorted by the keys in descending order.
%% @spec to_listr(Treap :: treap()) -> [{Key :: any(), Values :: [any()]}]
%% @end
%%--------------------------------------------------------------------
-spec to_listr(treap()) -> [{any(), any()}].
to_listr(Treap) ->
    Fun = fun(Key, Value, Acc) ->
		  [{Key, Value}|Acc]
	  end,
    %they come in reversed order, so use foldl
    foldl(Fun, [], Treap).

%%--------------------------------------------------------------------
%% @doc Converts a key/value list to a treap.
%% @spec from_list(List :: [{Key :: any(), Value :: any()}]) -> treap()
%% @end
%%--------------------------------------------------------------------
-spec from_list(list()) -> treap().
from_list(List)->
    T = treap:new(),
    Fun = fun({Key, Value}, Acc) ->
		  treap:append_list(Key, Value, Acc)
	  end,
    lists:foldl(Fun, T, List).

%%--------------------------------------------------------------------
%% @doc Do a level-order traversal and call Fun for every node ignoring its result.
%% @spec foreach(Fun :: function(Key :: any(), Values :: [any()]), Treap :: treap()) -> ok
%% @end
%%--------------------------------------------------------------------
-spec foreach(function(), treap()) -> ok.
foreach(_, empty) ->
    ok;
foreach(Fun, Treap) ->
    Queue = queue:in(Treap, queue:new()),
    Fun1 = fun(Qu, Self) ->
		   case queue:out(Qu) of
		       {empty, Qu} -> ok;
		       {{value, {_, Key, Values, Before, After}}, NewQu} ->
			   Fun(Key, Values),
			   Qu1 = case {Before, After} of
				     {empty, empty} ->
					 NewQu;   
				     {_, empty}->
					 queue:in(Before, NewQu);
				     {empty, _} ->
					 queue:in(After, NewQu);
				     _ -> 
					 queue:in(After, queue:in(Before, NewQu))
				 end,
			   Self(Qu1, Self)
		   end
	   end,
    Fun1(Queue, Fun1).

%%--------------------------------------------------------------------
%% @doc Traverse Treap in ascending order of the keys and call Fun on every node ignoring its result.
%% @spec foreachl(Fun :: function(Key :: any(), Values :: [any()]), Treap :: treap()) -> ok
%% @end
%%--------------------------------------------------------------------
-spec foreachl(function(), treap()) -> ok.
foreachl(_, empty) ->
    void;
foreachl(Fun, {_, Key, Values, Before, After}) ->
    foreachl(Fun, Before),
    Fun(Key, Values),
    foreachl(Fun, After).

%%--------------------------------------------------------------------
%% @doc Traverse Treap in descending order of the keys and call Fun on every node ignoring its result.
%% @spec foreachr(Fun :: function(Key :: any(), Values :: [any()]), Treap :: treap()) -> ok
%% @end
%%--------------------------------------------------------------------
-spec foreachr(function(), treap()) -> ok.
foreachr(_, empty) ->
    void;
foreachr(Fun, {_, Key, Values, Before, After}) ->
    foreachr(Fun, After),
    Fun(Key, Values),
    foreachr(Fun, Before).

%%--------------------------------------------------------------------
%% @doc Traverse Treap by starting a new process for every node and running Fun inside it.
%% @spec foreach_spawn(Fun :: function(Key :: any(), Values :: [any()]), Treap :: treap()) -> ok
%% @end
%%--------------------------------------------------------------------
-spec foreach_spawn(function(), treap()) -> ok.
foreach_spawn(_, empty) -> void;
foreach_spawn(Fun, Treap) ->
    spawn(fun() ->
		  foreach_spawn1(Fun, Treap)
	  end).

%%--------------------------------------------------------------------
%% @doc Call Fun on successive keys and values of Treap together with an extra argument Acc (short for accumulator). 
%% Fun must return a new accumulator which is passed to the next call. 
%% Acc is returned if the list is empty, else the result of the last call of Fun. 
%% The order of the handled keys is undefined (the treap is traversed in a level-order, 
%% which avoids using a stack and would use less memory than foldl and foldr for large treaps).
%% 
%% @spec fold(Fun :: function(Key :: any(), Values :: [any()], OldAcc :: any()), Acc :: any(), Treap :: treap()) -> NextAcc :: any()
%% @end
%%--------------------------------------------------------------------
-spec fold(function(), any(), treap()) -> any().
fold(_, Acc, empty) ->
    Acc;
fold(Fun, Acc, Treap) ->
    Queue = queue:in(Treap, queue:new()),
    Fun1 = fun(Qu, Acc1, Self) ->
		   case queue:out(Qu) of
		       {empty, Qu} -> Acc1;
		       {{value, {_, Key, Values, Before, After}}, NewQu} ->
			   Acc2 = Fun(Key, Values, Acc1),
			   Qu1 = case {Before, After} of
				     {empty, empty} ->
					 NewQu;   
				     {_, empty}->
					 queue:in(Before, NewQu);
				     {empty, _} ->
					 queue:in(After, NewQu);
				     _ -> 
					 queue:in(After, queue:in(Before, NewQu))
				 end,
			   Self(Qu1, Acc2, Self)
		   end
	   end,
    Fun1(Queue, Acc, Fun1).

%%--------------------------------------------------------------------
%% @doc Call Fun on successive keys and values of Treap together with an extra argument Acc (short for accumulator). 
%% Fun must return a new accumulator which is passed to the next call. 
%% Acc is returned if the list is empty, else the result of the last call of Fun. 
%% The keys are handled in ascending order.
%% 
%% @spec foldl(Fun :: function(Key :: any(), Values :: [any()], OldAcc :: any()), Acc :: any(), Treap :: treap()) -> NextAcc :: any()
%% @end
%%--------------------------------------------------------------------
-spec foldl(function(), any(), treap()) -> any().
foldl(_, Acc, empty) ->
    Acc;
foldl(Fun, Acc, {_, Key, Values, Before, After}) ->
    Acc1 = foldl(Fun, Acc, Before),
    Acc2 = Fun(Key, Values, Acc1),
    foldl(Fun, Acc2, After).

%%--------------------------------------------------------------------
%% @doc Call Fun on successive keys and values of Treap together with an extra argument Acc (short for accumulator). 
%% Fun must return a new accumulator which is passed to the next call. 
%% Acc is returned if the list is empty, else the result of the last call of Fun. 
%% The keys are handled in descending order.
%% 
%% @spec foldr(Fun :: function(Key :: any(), Values :: [any()], OldAcc :: any()), Acc :: any(), Treap :: treap()) -> NextAcc :: any()
%% @end
%%--------------------------------------------------------------------
-spec foldr(function(), any(), treap()) -> any().
foldr(_, Acc, empty) ->
    Acc;
foldr(Fun, Acc, {_, Key, Values, Before, After}) ->
    Acc1 = foldr(Fun, Acc, After),
    Acc2 = Fun(Key, Values, Acc1),
    foldr(Fun, Acc2, Before).

%%--------------------------------------------------------------------
%% @doc Returns a printable XML represnetation of the treap as an IoList
%% The keys in the returned XML are sorted in ascending order.
%%
%% WARNING! This is an experimental function and may have issues with complex 
%% key or value types.
%%
%% @spec to_xml(Treap :: treap()) -> XML :: iolist()
%% @end
%%--------------------------------------------------------------------
-spec to_xml(treap()) -> iolist().
to_xml(Treap) ->
    ValueFormatter = fun(Value, Acc) ->
			     [io_lib:format("~n<value>~w</value>", [Value])|Acc] 
		     end,
    Fun = fun(Key, Values, Acc) ->
		  [Acc, io_lib:format("~n<node>~n<key>~w</key>", [Key]), lists:foldl(ValueFormatter, [], Values), "\n</node>"]
	  end,
    ["<treap>", foldl(Fun, [], Treap), "\n</treap>"].		     

%%--------------------------------------------------------------------
%% @doc Returns a printable JSON represnetation of the treap as an IoList
%% The keys in the returned JSON are sorted in ascending order.
%%
%% WARNING! This is an experimental function and may have issues with complex 
%% key or value types.
%%
%% @spec to_json(Treap :: treap()) -> JSON :: iolist()
%% @end
%%--------------------------------------------------------------------
-spec to_json(treap()) -> iolist().
to_json(Treap) ->
    ValueFormatter = fun(Value, Acc) ->
			     [io_lib:format(", \"~w\"", [Value])|Acc]
		     end, 
    Fun = fun(Key, Values, Acc) ->
		  [[$,|[$ |First]]|Rest] = lists:reverse(lists:foldl(ValueFormatter, [], Values)),
		  Format = case Acc of
			       [] ->"~n\"~w\":[";
			       _ -> ",~n\"~w\":["
			  end,
		  [Acc, io_lib:format(Format, [Key]), First, Rest, "]"]
	  end,
    ["{", foldl(Fun, [], Treap), "\n}"].

%%--------------------------------------------------------------------
%% @doc Returns a new dictionary containing the same key/values mappings as Treap.
%% @spec to_dict(Treap :: treap()) -> Dict :: dict:dictionary()
%% @end
%%--------------------------------------------------------------------
-spec to_dict(treap()) -> dict:dictionary().
to_dict(Treap) ->
    D = dict:new(),
    to_dict(Treap, D).

%%--------------------------------------------------------------------
%% @doc Returns a dictionary resulting from adding all the key/values mappings 
%% from Treap to the existing dictionary Dict. If a key is already present 
%% the behavior is like calling dict:append_list(Key, treap::fetch(Key, Treap)).
%%
%% @spec to_dict(Treap :: treap(), Dict :: dict:dictionary()) -> NewDict :: dict:dictionary()
%% @end
%%--------------------------------------------------------------------
-spec to_dict(treap(), dict:dictionary()) -> dict:dictionary().
to_dict(Treap, Dict) ->
    Fun = fun(K,V,D) ->
		  dict:append_list(K, V, D)
	  end,
    fold(Fun, Dict, Treap).

%%--------------------------------------------------------------------
%% @doc Returns a new treap containing the same key/values mappings as Dict.
%% @spec from_dict(Dict :: dict:dictionary()) -> Treap :: treap()
%% @end
%%--------------------------------------------------------------------
-spec from_dict(dict:dictionary()) -> treap().
from_dict(D) ->
    T = new(),
    from_dict(D, T).

%%--------------------------------------------------------------------
%% @doc Returns a treap resulting from adding all the key/values mappings 
%% from Dict to the existing treap Treap. If a key is already present 
%% the behavior is like calling treap:append_list(Key, dict::fetch(Key, Dict)).
%%
%% @spec from_dict(Dict :: dict:dictionary(), Treap :: treap()) -> NewTreap :: treap()
%% @end
%%--------------------------------------------------------------------
-spec from_dict(dict:dictionary(), treap()) -> treap().
from_dict(D, Tr) ->
    Fun = fun(K, V, T) ->
		  treap:append_list(K, V, T)
	  end,
    dict:fold(Fun, Tr, D).

%%--------------------------------------------------------------------
%% @doc Returns the number of elements in dict.
%% @spec size(Treap :: treap()) -> Size :: integer()
%% @end
%%--------------------------------------------------------------------
-spec size(treap()) -> integer().
size(Treap) ->
    Fun = fun(_, _, Count) ->
			  Count + 1
		  end,
    fold(Fun, 0, Treap).

%%--------------------------------------------------------------------
%% @doc Returns the the total number of all items stored in the treap.
%% @spec count_values(Treap :: treap()) -> Count :: integer()
%% @end
%%--------------------------------------------------------------------
-spec count_values(treap()) -> integer().
count_values(Treap) ->
    Fun = fun(_, V, Count) ->
			  Count + length(V)
		  end,
    fold(Fun, 0, Treap).

%%--------------------------------------------------------------------
%% @doc Update the a value in a treap by calling Fun on the value to get a new value. 
%% An exception is generated if Key is not present in the treap.
%% If Fun returns a non-empty list it is directly used as the new value, else
%% the result is enclosed in a list.
%%
%% @spec update(Key :: any(), Fun :: function(Values :: [any()]), Treap :: treap()) -> NewTreap :: treap()
%% @end
%%--------------------------------------------------------------------
-spec update(any(), function(), treap()) -> treap().
update(Key, _, empty) ->
    erlang:error({not_found, Key});
update(Key, Fun, {P, Key, Values, Before, After}) ->
    NewValue = case Fun(Values) of
		   [_|_] = Result -> Result;
		   Result -> [Result]
	       end,
    {P, Key, NewValue, Before, After};
update(Key, Fun, {P, NodeKey, Values, Before, After}) when Key < NodeKey ->
    {P, NodeKey, Values, update(Key, Fun, Before), After};
update(Key, Fun, {P, NodeKey, Values, Before, After}) ->
    {P, NodeKey, Values, Before, update(Key, Fun, After)}.

%%--------------------------------------------------------------------
%% @doc Update the a value in a treap by calling Fun on the value to get a new value. 
%% If Key is not present in the treap then Initial will be stored as the first value.
%% If Fun returns a non-empty list it is directly used as the new value, else
%% the result is enclosed in a list.
%%
%% @spec update(Key :: any(), Fun :: function(Values :: [any()]), Initial :: any(), Treap :: treap()) -> NewTreap :: treap()
%% @end
%%--------------------------------------------------------------------
-spec update(any(), function(), any(), treap()) -> treap().
update({?SPLIT_TAG, _} = Split, _, Value, empty) ->%splitting the treap
    {?MAX_PRIORITY, Split, [Value], empty, empty};
update(Key, _, [_|_] = Initial, empty) ->
    {random_priority(), Key, Initial, empty, empty};
update(Key, _, Initial, empty) ->
    {random_priority(), Key, [Initial], empty, empty};
update({?SPLIT_TAG, Key} = Split, Fun, Value, {_, NodeKey, _, Before, After} = Parent) ->
    case Key >= NodeKey of
	true ->
	    rotate_left(Parent, update(Split, Fun, Value, After));
	_ ->
	    rotate_right(Parent, update(Split, Fun, Value, Before))
    end;
update(Key, Fun, _, {NodePriority, Key, NodeValue, Before, After}) -> %key match
    NewValue = case Fun(NodeValue) of
		   [_|_] = Result -> Result;
		   Result -> [Result]
	       end,
    {NodePriority, Key, NewValue, Before, After};
update(Key, Fun, Value, {_, NodeKey, _, _, After} = Parent) when Key >= NodeKey ->
    rotate_left(Parent, update(Key, Fun, Value, After));
update(Key, Fun, Value, {_, _, _, Before, _} = Parent) ->
    rotate_right(Parent, update(Key, Fun, Value, Before)).

%%--------------------------------------------------------------------
%% @doc Add Inc to the value associated with Key and store the new value. 
%% If Key is not present in the treap then Inc will be stored as the first value.
%%
%% @spec update_counter(Key :: any(), Inc :: number(), Treap :: treap()) -> NewTreap :: treap()
%% @end
%%--------------------------------------------------------------------
-spec update_counter(any(), number(), treap()) -> treap().
update_counter(Key, Inc, empty) when is_number(Inc) ->
    {random_priority(), Key, [Inc], empty, empty};
update_counter(Key, Inc, {P, Key, [Value], Before, After}) ->
    {P, Key, [Value + Inc], Before, After};
update_counter(Key, Inc, {P, NodeKey, Value, Before, After}) when Key < NodeKey ->
    {P, NodeKey, Value, update_counter(Key, Inc, Before), After};
update_counter(Key, Inc, {P, NodeKey, Value, Before, After}) ->
    {P, NodeKey, Value, Before, update_counter(Key, Inc, After)}.

debug_tree(empty) ->empty;
debug_tree({P, K, _, B, A}) ->
    [{P, K}, debug_tree(B), debug_tree(A)].

%%%===================================================================
%%% Internal functions
%%%===================================================================
random_priority()->
    random:uniform(?MAX_PRIORITY) - 1.

foreach_spawn1(Fun, {_, Key, Values, Before, After}) ->
    case Before of
	empty -> void;
	_ -> spawn(fun()->foreach_spawn1(Fun, Before) end)
    end,
    case After of
	empty -> void;
	_ -> spawn(fun()->foreach_spawn1(Fun, After) end)
    end,
    Fun(Key, Values).

rotate_right({ParentP, ParentK, ParentV, _, ParentAfter}, {BeforeP, BeforeK, BeforeV, BeforeBefore, BeforeAfter}) when ParentP < BeforeP ->
    {BeforeP, BeforeK, BeforeV, BeforeBefore, {ParentP, ParentK, ParentV, BeforeAfter, ParentAfter}};
rotate_right({ParentP, ParentK, ParentV, _, ParentAfter}, Before) ->
    {ParentP, ParentK, ParentV, Before, ParentAfter}.

rotate_left({ParentP, ParentK, ParentV, ParentBefore, _}, {AfterP, AfterK, AfterV, AfterBefore, AfterAfter}) when ParentP < AfterP ->
    {AfterP, AfterK, AfterV, {ParentP, ParentK, ParentV, ParentBefore, AfterBefore}, AfterAfter};
rotate_left({ParentP, ParentK, ParentV, ParentBefore, _}, After) ->
    {ParentP, ParentK, ParentV, ParentBefore, After}.
